class Solution
{
public:
    // 求解齐次线性差分方程后得到通项公式, 直接计算, 但是中间结果会溢出
    int numberOfWays(string s, string t, long long k)
    {
        int n = s.size();

        s += s;
        auto pos = s.find(t);
        if (pos == string::npos)
        {
            return 0;
        }
        auto pos2 = s.find(t, pos + 1);

        vector<int> target;
        target.push_back(pos);
        if (pos2 != string::npos)
        {
            int period = pos2 - pos;
            for (int i = pos2; i < n; i += period)
            {
                target.push_back(i);
            }
        }

        long long p = 1;
        long long nm1 = n - 1;
        int originK = k;

        // 结果需要模1000000007, 但中间涉及除法, 所以中间需要模 n*1000000007ll, 这会导致溢出
        long long mod = 1000000007ll;
        long long nmod = n * mod;
        while (k)
        {
            if (k & 1)
            {
                p = p * nm1 % nmod;
            }
            nm1 = nm1 * nm1 % nmod;
            k >>= 1;
        }

        int sign = (originK & 1) ? -1 : 1;

        long long dp0 = p + sign * (n - 1);
        long long dp1 = p - sign;

        dp0 = dp0 % nmod / n % mod;
        dp1 = dp1 % nmod / n % mod;

        long long result = 0;

        for (int t : target)
        {
            if (t == 0)
            {
                result += dp0;
            }
            else
            {
                result += dp1;
            }
        }
        return result % mod;
    }
};